/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2022-09-07
 * Time:23:46
 */

/**
 * 力扣148:排列链表
 */

// 归并排序---递归
//先分解再合并
public class sortList {

    public ListNode sortList(ListNode head) {
        return sortList(head, null);
    }

    public ListNode sortList(ListNode head, ListNode tail) {
        if (head == null) {
            return head;
        }
        if (head.next == tail) {
            head.next = null;
            return head;
        }
        ListNode slow = head, fast = head;
        while (fast != tail) {
            slow = slow.next;
            fast = fast.next;
            if (fast != tail) {
                fast = fast.next;
            }
        }
        ListNode mid = slow;
        ListNode list1 = sortList(head, mid);
        ListNode list2 = sortList(mid, tail);
        ListNode sorted = merge(list1, list2);
        return sorted;
    }

    public ListNode merge(ListNode head1, ListNode head2) {
        ListNode dummyHead = new ListNode(0);
        ListNode temp = dummyHead, temp1 = head1, temp2 = head2;
        while (temp1 != null && temp2 != null) {
            if (temp1.val <= temp2.val) {
                temp.next = temp1;
                temp1 = temp1.next;
            } else {
                temp.next = temp2;
                temp2 = temp2.next;
            }
            temp = temp.next;
        }
        if (temp1 != null) {
            temp.next = temp1;
        } else if (temp2 != null) {
            temp.next = temp2;
        }
        return dummyHead.next;
    }

    /**
     * 归并排序
     */
    // 归并排序---递归
    //先分解再合并
    public static void mergeSort(int[] array){
        mergeDecompose(array,0,array.length - 1);
    }

    //分解
    public static void mergeDecompose(int[] array,int left, int right){
        if (left >= right){
            return;
        }

        //取得中间位置的值,左右分割
        int mid = (left + right)/2;

        //先分解左边
        mergeDecompose(array,left,mid);

        //再分解右边
        mergeDecompose(array,mid + 1,right);

        //开始进行合并
        merge(array,left,right,mid);
    }

    //合并
    public static void merge(int[] array,int left,int right,int mid){
        //创建一个临时数组
        int[] tmp = new int[right - left + 1];
        int k = 0;

        int l1 = left;
        int l2 = mid + 1;

        //两个不同的数列进行合并,不能越界
        while (l1 <= mid && l2 <= right){
            if (array[l1] < array[l2]){
                tmp[k] = array[l1];
                k++;
                l1++;
            }else{
                tmp[k] = array[l2];
                k++;
                l2++;
            }
        }
        //因为两个数列的大小不一,可能前一个已经全部排进新的数组了,但是后一个还没有排完
        //当l1中还未排完时
        while (l1 <= mid){
            tmp[k] = array[l1];
            k++;
            l1++;
        }
        //当l2中还未排完时
        while (l2 <= mid){
            tmp[k] = array[l2];
            k++;
            l2++;
        }

        //将已经排好序的数组拷贝到原数组当中
        for (int i = 0; i < k; i++) {
            //因为可能不止一组数据需要再次传入,所以我们需要加上一个left
            array[i + left] = tmp[i];
        }
    }
}
